import java.util.List;

/**
 * 面试题 08.06. 汉诺塔问题
 * https://leetcode.cn/problems/hanota-lcci/description/
 */
class Solution4 {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if(A.size() == 1) C.add(A.remove(A.size() - 1));
        dfs(A, C, B, n - 1);
        C.add(A.remove(A.size() - 1));
        dfs(B, A, C, n - 1);
    }
}